// 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
// 请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

// 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

// 此外：
// 应当保持奇数节点和偶数节点的相对顺序。
// 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

const oddEvenList = function (head: ListNode | null): ListNode | null {
    // 安全检测
    if (head === null) {
        return head;
    }
    let odd: ListNode = head;// 奇数链表
    let even: ListNode = head.next;// 偶数链表
    let evenHead: ListNode = even;// 偶数链表头节点
    // 双指针操作，注意循环条件
    while (odd && even && even.next) {
        odd.next = even.next;
        even.next = even.next.next
        odd = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;
};


// 这道题目是一道比较容易想偏的题目
// 如果你的第一反应是想要交换链表那基本上就走远了
// 其实对于链表来说，交换节点操作并不常见
// 针对于这道题目，其实考察的还是链表的常规指针操作
// 首先我们思考对于题目中要满足的相对顺序要求，其实只要你分别按照顺序
// 串联得到奇数节点组成的链表和偶数节点组成的链表共两条，
// 然后将奇数链表的末节点和偶数链表的头节点相连即可满足题目中的要求
// 所以这道题我们也是使用双指针的一个思路，建议在纸上画一画
// 先保存一下偶数链表头节点，然后再让双指针开始走，按照顺序来一次链接
// 最后奇数链表的末节点链接之前保存的偶数链表的头节点即可得到结果